package com.hanxiaozhang.no10leetcode.array;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给定一个有序数组和一个目标值，返回目标值在数组中的下标，如果没有的话则返回在数组中应插入位置的数组下标。
 * 你可以假定数组中没有重复元素
 * 示例1：
 * 输入: [1,3,5,6], 5
 * 输出: 2
 * 示例2:
 * 输入: [1,3,5,6], 2
 * 输出: 1
 * <p>
 * 思路：
 * 1. 二分法找到该元素，直接返回
 * 2. 二分法没有找到该元素，找到最后一个数，来判断插入位置：
 * - 如果最后一个数大于等于目标值的话，目标值插入左边界位置即可；
 * - 如果最后一个数小于目标值，则需要插入左边界值+1即可
 *
 * @author hanxinghua
 * @create 2024/1/12
 * @since 1.0.0
 */
public class No35SearchInsertPosition {

    public static void main(String[] args) {

        int[] arr = {1, 3, 5, 6};
        int target = 2;

        method1(arr, target);

    }


    /**
     * 方法1
     *
     * @param arr
     * @param target
     * @return
     */
    private static int method1(int[] arr, int target) {

        // 二分法找到该元素，直接返回
        int left = 0, right = arr.length - 1, mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == arr[mid]) {
                return mid;
            } else if (target > arr[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 二分法没有找到该元素，找到最后一个数，来判断插入位置：
        // 如果最后一个数大于等于目标值的话，目标值插入左边界位置即可；
        // 如果最后一个数小于目标值，则需要插入左边界值+1即可
        if (arr[left] >= target) {
            return left;
        } else {
            return left + 1;
        }


    }

}
